/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    bool hasCycle(ListNode *head) 
    {
        if(head == nullptr || head->next == nullptr)// || 前的条件成立不会执行后面的条件
            return false;
        ListNode* slow = head;
        ListNode* fast = head->next;// 因为要让fast去追slow，所以其实位置要不同
        while(fast != slow)
        {
            if(fast == nullptr || fast->next == nullptr)
                return false;
            slow = slow->next;
            fast = fast->next->next;    
        }    
        
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        if(head == nullptr || head->next == nullptr)
            return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;

        while(1)
        {
            if(fast == nullptr || fast->next == nullptr)
                return nullptr;
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)    
                break;
        }

        ListNode* start = head;
        while(start != slow)
        {
            slow = slow->next;
            start = start->next;
        }  
        return start;

    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* guard = new ListNode;//哨兵位头节点
        ListNode* cur1 = l1, *cur2 = l2, *tail = guard;
        int flag = 0; //保存结果
    
        while(cur1 || cur2)
        {
            if(cur1)
                flag += cur1->val;
            if(cur2)
                flag += cur2->val;
            
            if(flag < 10)
            {
                ListNode* tmp = new ListNode(flag);
                tail->next = tmp;//尾插
                tail = tmp;
                flag = 0;
            }
            else
            {
                ListNode* tmp = new ListNode(flag % 10);
                tail->next = tmp;//尾插
                tail = tmp;
                flag /= 10;
            }

            if(cur1)
                cur1 =cur1->next;
            if(cur2)
                cur2 = cur2->next;
        }
        if(flag)//特殊进位情况
        {
            ListNode* tmp = new ListNode(flag);
            tail->next = tmp;
            tail = tmp;
        }
        
        tail = guard->next;
        delete guard;

        return tail;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution 
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        //处理边界情况
        if(head == nullptr)
            return nullptr;
        if(head->next == nullptr)
            return head;

        //定义哨兵位头节点
        ListNode *guard = new ListNode;
        guard->next = head;
        ListNode *prev = guard;
        ListNode *cur = head;
        ListNode *next = cur->next;
        ListNode* nnext = next->next;
        
        while(cur)
        {
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
            if(cur == nullptr)
                break;
            next = cur->next;
            if(next == nullptr)
                break;
            nnext = next->next;

        }
        ListNode *ret = guard->next;
        delete guard;
        return ret;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution 
{
public:
    void reorderList(ListNode* head) 
    {
        //处理边界
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
            return;
        //1.找中间节点
        ListNode *slow = head, *fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        //此时slow就是链表的中间节点
        //2.逆序后半部分链表
        ListNode* head2 = new ListNode;
        ListNode *cur = slow->next;
        slow->next = nullptr;//断开链表
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }
        //3.合并两段链表
        ListNode *cur1 = head, *cur2 = head2->next, *guard = new ListNode;
        cur = guard; 
        while(cur1)//由于是slow->next位置开始划分，cur1一定更长
        {
            cur->next = cur1;
            cur1=cur1->next;
            cur = cur->next;
            if(cur2)
            {
            cur->next = cur2;
            cur2=cur2->next;
            cur = cur->next;
            }
        }
        delete head2;
        delete guard;
    }
};
